package com.itheima.leetcode.od.b.stack;

import java.util.LinkedList;

/**
 * (C卷,100分)- 表达式括号匹配（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * (1+(2+3)*(3+(8+0))+1-2)这是一个简单的数学表达式,今天不是计算它的值,而是比较它的括号匹配是否正确。
 * <p>
 * 前面这个式子可以简化为(()(()))这样的括号我们认为它是匹配正确的,
 * <p>
 * 而((())这样的我们就说他是错误的。注意括号里面的表达式可能是错的,也可能有多个空格，对于这些我们是不用去管的，
 * <p>
 * 我们只关心括号是否使用正确。
 * <p>
 * 输入描述
 * <p>
 * 给出一行表达式(长度不超过 100)。
 * <p>
 * 输出描述
 * <p>
 * 如果匹配正确输出括号的对数，否则输出-1。
 * <p>
 * 用例
 * <p>
 * 输入	(1+(2+3)*(3+(8+0))+1-2)
 * 输出	4
 * 说明	无
 * <p>
 * 题目解析
 * <p>
 * 本题就是括号匹配的变种题，只是加入了一些干扰字符，我们可以用正则去掉非()的字符，然后利用栈结构校验括号是否成对，可以参考LeetCode - 20 有效的括号_伏城之外的博客-CSDN博客
 */
public class BracketMatching {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();*/

        String input = "(1+(2+3)*(3+(8+0))+1-2)";
        System.out.println(getResult(input));
    }

    public static int getResult(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(')');
            } else if (c == ')') {
                if (!stack.isEmpty() && c == stack.peek()) {
                    stack.pop();
                    count++;
                } else {
                    return -1;
                }
            }
        }
        return stack.isEmpty() ? count : -1;
    }
}